package com.jjlin.chapter_3;

import java.util.*;
import java.lang.*;

public class CD174{
    //二叉树节点
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static TreeNode createBinaryTree(int[][] nums, int root){
        HashMap<Integer, TreeNode> map = new HashMap<>();
        int rows = nums.length;
        int cols = nums[0].length;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(nums[i][j] != 0 && !map.containsKey(nums[i][j]))
                    map.put(nums[i][j], new TreeNode(nums[i][j]));

        for(int i = 0; i < rows; i++){
            TreeNode node = map.get(nums[i][0]);
            if(nums[i][1] != 0){
                node.left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                node.right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //判断二叉树是否为二叉搜索树
    public static boolean isBST(TreeNode root){
        if(root == null)
            return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int pre = Integer.MIN_VALUE;
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                if(cur.val <= pre)
                    return false;
                pre = cur.val;
                cur = cur.right;
            }
        }
        return true;
    }

    //判断二叉树是否为完全二叉树
    public static boolean isCBT(TreeNode root){
        if(root == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leaf = false;
        TreeNode left = null;
        TreeNode right = null;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            left = node.left;
            right = node.right;
            if((leaf && (left != null || right != null)) || (left == null && right != null))
                return false;
            if(left != null)
                queue.offer(left);
            if(right != null){//说明left != null
                queue.offer(right);
            }else{//说明left == null
                leaf = true;
            }
        }
        return true;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        TreeNode head = createBinaryTree(nums, root);
        System.out.println(isBST(head));
        System.out.println(isCBT(head));
    }
}



